package org.algorithm.biubiu.wheel_1.链表;

import org.algorithm.biubiu.wheel_1.common.ListNode;
import org.junit.Test;

import java.util.ArrayList;

/**
 * @Date 2022/2/21 17:38
 * @Created by biubiu
 * @Link {}
 */
public class 链表排序 {


    @Test
    public void test() {
        ListNode listNode = sortList(ListNode.build(3,2,4));
        System.out.println("listNode = " + listNode);
    }

    public ListNode sortList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode[] nodeArr = listToArr(head);
        quickSort(nodeArr, 0, nodeArr.length - 1);
        return arrToNode(nodeArr);
    }

    public ListNode[] listToArr(ListNode head) {
        ArrayList<ListNode> node = new ArrayList<ListNode>();
        ListNode dummy = head;
        while (dummy != null) {
            node.add(dummy);
            dummy = dummy.next;
        }
        ListNode[] arr = new ListNode[node.size()];
        node.toArray(arr);
        return arr;
    }

    public static void quickSort(ListNode[] target, int left, int right) {
        if (left >= right) {
            return;
        }
        ListNode pivotNode = target[left];
        int pivot = pivotNode.val;
        int leftIndex = left;
        int rightIndex = right;
        ListNode temp;
        while (leftIndex < rightIndex) {

            while (target[rightIndex].val >= pivot && leftIndex < rightIndex) {
                rightIndex--;
            }

            while (target[leftIndex].val <= pivot && leftIndex < rightIndex) {
                leftIndex++;
            }
            if (leftIndex < rightIndex) {
                temp = target[leftIndex];
                target[leftIndex] = target[rightIndex];
                target[rightIndex] = temp;
            }
        }
        target[left] = target[rightIndex];
        target[rightIndex] = pivotNode;

        quickSort(target, left, leftIndex - 1);
        quickSort(target, leftIndex + 1, right);
    }

    public ListNode arrToNode(ListNode[] arr) {
        ListNode prev = null;
        for (ListNode node : arr) {
            if (prev == null) {
                prev = node;
            } else {
                prev.next = node;
                prev = node;
            }
        }
        arr[arr.length-1].next = null;
        return arr[0];
    }
}
